#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "../min_list/time_printer.h"

#define BLOOM_SIZE 2048  // 位数组的大小 (bit count)
#define NUM_HASHES 10     // 使用的哈希函数数量

typedef struct {
    unsigned char bit_array[BLOOM_SIZE / 8];  // 位数组 (字节表示)
} BloomFilter;

// 简单的哈希函数示例，使用两个不同的种子
unsigned int hash1(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

unsigned int hash2(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

// 初始化布隆过滤器
void bloom_init(BloomFilter *bloom) {
    memset(bloom->bit_array, 0, sizeof(bloom->bit_array));
}

// 添加元素到布隆过滤器
void bloom_add(BloomFilter *bloom, unsigned int element) {
    for (int i = 0; i < NUM_HASHES; i++) {
        unsigned int hash_val = (hash1(element) + i * hash2(element)) % BLOOM_SIZE;
        bloom->bit_array[hash_val / 8] |= (1 << (hash_val % 8));
    }
}

// 检查元素是否在布隆过滤器中
int bloom_check(BloomFilter *bloom, unsigned int element) {
    for (int i = 0; i < NUM_HASHES; i++) {
        unsigned int hash_val = (hash1(element) + i * hash2(element)) % BLOOM_SIZE;
        if (!(bloom->bit_array[hash_val / 8] & (1 << (hash_val % 8)))) {
            return 0;  // 未找到该元素
        }
    }
    return 1;  // 可能存在该元素
}

int main() {
    int a=0;
    void* timer = init_record_time_printer("vector computer");
    BloomFilter bloom;
    bloom_init(&bloom);

    record_time_printer(timer, "init done");

    // // 添加一些节点到布隆过滤器中
    // bloom_add(&bloom, 12345);
    // bloom_add(&bloom, 67890);
    // bloom_add(&bloom, 54321);
    for(int i=0; i<1000; i++){
        bloom_add(&bloom, ((i*23)<<(i%3))*(i*i));
    }

    record_time_printer(timer, "add point done");

    // 检查节点是否出现过
    for(int i=0; i<1000; i++){
        if(bloom_check(&bloom, i)){
            a++;
        }
    }

    record_time_printer(timer, "check point done");
    record_last_time(timer);
    printf("a is %d\n",a);

    return 0;
}
